//
// Created by denglibin on 2020/6/30.
// leetcode 739. 每日温度

// 请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
//
//例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
//

#include <stdio.h>
#include <stdlib.h>
/**
 * 温度入栈 入栈规则：如果新入栈的温度比栈顶的温度高，则入栈失败
 * @param T 温度数组
 * @param index  要入栈的温度的下表
 * @param stack  栈
 * @param stackPointer 栈顶指针
 * @return 1 入栈成功，0 入栈失败
 */
static int pushTemperature(int * T, int index, int * stack, int *stackPointer){

    if(*stackPointer < 0 || T[index] <= T[stack[*stackPointer]]) {
        // 直接入栈
        (*stackPointer)++;
        stack[*stackPointer] = index;
        return 1;
    }
    return 0;
}

/**
 * 每日温度
 * 思路： 使用栈实现
 * @param T
 * @param TSize
 * @param returnSize
 * @return
 */
static int* dailyTemperatures(int* T, int TSize, int* returnSize){
    *returnSize = TSize;
    int *stack = (int *)calloc(TSize, sizeof(int )); // 用一个数组来代表栈 （栈中保存的是数组T的下标）
    int stackPointer = -1; // 栈顶指针
    int *arr = (int *)calloc(TSize, sizeof(int )); // 用一个数组保存结果

    for(int i = 0; i < TSize; i++){

        while (!pushTemperature(T, i, stack, &stackPointer)){ // 入栈失败 说明入栈的温度比栈顶温度大
            // 弹出栈顶温度
            arr[stack[stackPointer]] = i-stack[stackPointer]; // 保存结果
            stackPointer--; // 栈顶指针减1
        }
    }
    free(stack);
    return arr;
}

static int main1(){
    int temperatures[] = {73, 74, 75, 71, 69, 72, 76, 73};
    int returnSize;
    int *result = dailyTemperatures(temperatures, sizeof(temperatures)/sizeof(int), &returnSize);
    for(int i = 0; i < returnSize;i++){
        printf("%d ", result[i]);
    }
    free(result);
    return 0;
}